package algorithm.string;

import util.GsonUtil;

/**
 * leetcode : https://leetcode.com/problems/implement-strstr/description/
 * 28. Implement strStr()
 * Difficulty : Easy
 *
 * 在一个大字符串Str中，找到匹配小字符串 s 的头索引
 * 举栗：
 * Input: haystack = "hello", needle = "ll"
 * Output: 2
 *
 * 思路：
 * 1) 暴力求解
 * 2) 使用KMP算法。
 *
 * 参考:
 * 字符串匹配算法——BM, Horspool, Sunday, KMP, KR, AC 算法一网打尽：https://blog.csdn.net/qiudesuo/article/details/84319371
 * https://blog.csdn.net/cristianojason/article/details/51235301
 * https://blog.csdn.net/v_july_v/article/details/7041827 (理解KMP)
 *
 * @Author Antony
 * @Since 2018/8/1 19:23
 */
public class ImplementstrStr {
    //TODO

    public static void main(String[] args) {
//        String hay = "mississippi";
//        String needle = "issippi";
//        String hay = "aaaaa";
//        String needle = "bba";
        String hay = "";
        String needle = "a";

        String hay_1 = "Here is a simple example";
        String needle_1 = "example";

//        System.out.println(strStr_BF(hay, needle));
        System.out.println(strStr_RK(hay_1, needle_1));
        System.out.println(strStr_BM(hay_1, needle_1));

        System.out.println(GsonUtil.toJson(makeSkip(needle_1)));
    }


    public static int strStr_kmp(String haystack, String needle) {
        if(needle.length() == 0) return 0;


        return 0;
    }


    /**
     * Boyer-Moore算法(BM算法):
     * 详解1：https://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
     * 详解2：https://blog.csdn.net/qq_21201267/article/details/92799488
     *
     * 基于后缀匹配的模式串匹配算法.
     * 需要定义两个规则：然后在遇到不匹配字符时，从坏字符和好后缀中，选一个可以跳跃最长的，往后跳
     * 1、坏字符规则. 从后往前匹配，遇到不匹配的字符。
     *      a)如果该字符在匹配串中没出现，则匹配串往后移动到坏字符后+1的位置
     *      b)否则，移动到第一个在匹配串中出现的位置并对齐
     * 2、好后缀规则.
     *      a)模式串中子串匹配到了好后缀,则移动匹配串和好后缀对齐
     *      b)模式串中没有匹配到好后缀,则需要寻找匹配串的一个最长前缀,并让该前缀等于好后缀的后缀
     *      c)匹配串中一个字符也没匹配到好后缀，则匹配串移动到好后缀+1位置
     *
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr_BM(String haystack, String needle){
        if(needle.length() == 0) return 0;

        int needleLen = needle.length();            // 模式串长度
        int[] skipArr = makeSkip(needle);           // (坏字符匹配)模式串中的char字符,在模式串中的位置, idx为字符char值,val为位置.
//        int[] shiftArr = makeShift(needle);

        int moveIdx = needleLen-1;  // 匹配移动的浮标
        while(moveIdx < haystack.length()){
            int endIdx=moveIdx;
            int i=needleLen-1;
            while(i>=0){
                if(needle.charAt(i) != haystack.charAt(endIdx)){
                    break;
                }
                i--;
                endIdx--;
            }
            if(i==-1){
                return endIdx+1;
            }
            int skip = needleLen - skipArr[(int)(needle.charAt(i))];
            moveIdx = moveIdx + skip;
        }

        return -1;
    }

    /** [坏字符] 构建skip数组，利用字符的Hash来映射单字符，在模式串中的位置 */
    private static int[] makeSkip(String needle){
        int[] skip = new int[256];
        for(int i=0; i<skip.length; i++){
            skip[i] = -1;
        }

        // 从后往前赋值，确保重复出现的字符，idx为最靠前
        for(int i=0; i<needle.length(); i++){
            char c = needle.charAt(i);
            skip[(int)c] = i;
        }
        return skip;
    }

    /** [好后缀] */
    private static int[] makeShift(String needle){

        return null;
    }


    /**
     * 字符串匹配-Sunday算法:https://blog.csdn.net/q547550831/article/details/51860017
     *
     * 是在BM算法上的改进
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr_sunday(String haystack, String needle) {
        if(needle.length() == 0) return 0;


        return 0;
    }


    /**
     * RunTime 3ms, Faster than 31.04%
     * Memory 42.6MB, less than 6.10%
     *
     * 在BF的基础上做的优化，匹配子串的hashCode
     * 由于hashCode存在冲突的可能，当hashCode相等时，再比较字符串。
     * hashCode可以设计一个简单的算法，然后下一个子串的hashCode可以由上一个子串的hashCode进行增量计算而来，从而简化计算
     *
     * 时间复杂度 O(N)
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr_RK(String haystack, String needle){
        if(needle.length() ==0) return 0;
        int haySize = haystack.length();
        int needleSize = needle.length();

        if(haySize >= needleSize){
            int needleHash = needle.chars().sum();
            int tmpHash = haystack.substring(0,needleSize).chars().sum();

            int topIdx = 0;
            int endIdx = needleSize;
            while (endIdx <= haySize){
                if(needleHash==tmpHash && compareStr(needle, haystack, topIdx, endIdx)){
                    return topIdx;
                }

                if(endIdx < haySize){
                    tmpHash = tmpHash - haystack.charAt(topIdx) + haystack.charAt(endIdx);
                }
                topIdx++;
                endIdx++;
            }
        }

        return -1;
    }

    private static boolean compareStr(String needle, String hay, int hayStart, int hayEnd){
        int needleIdx = 0;
        for(int i=hayStart; i<hayEnd; i++){
            if(needle.charAt(needleIdx) != hay.charAt(i)){
                return false;
            }
            needleIdx++;
        }
        return true;
    }



    /**
     * beats 45.26% - 6ms
     * 暴力匹配  (BF算法)
     * 时间复杂度,最差的情况下是 O(MxN)
     *
     * 注意:
     * hayStack只要匹配到 haySize-needleSize+1 即可,因为再往后hayStack的长度以及小于needle了，肯定不匹配
     * 要注意needle.length 大于 hayStack的情况（其实在第一层for循环的条件已经做了判断了）
     */
    public static int strStr_BF(String haystack, String needle) {
        if(needle.length() ==0) return 0;
        int haySize = haystack.length();
        int needleSize = needle.length();
        for(int i=0; i<haySize-needleSize+1; i++){
            for(int j=0; j<needleSize; j++){
                if(needle.charAt(j) != haystack.charAt(i+j)){
                    break;
                }
                // 如果匹配j到needle最后一个都通过了，那么这时候就可以返回i当结果了
                if(j == needle.length()-1) return i;
            }
        }
        return -1;
    }
}
